class Graph {
    constructor(isDirected = false) {
        this.isDirected = isDirected;
        this.vertices = [];
        this.adjList = new Map();
    };
    addVertex(v) {
        if (!this.vertices.includes(v)) {
            this.vertices.push(v);
            this.adjList.set(v, []);
        }
    };
    addEdge(v, w) {
        if (!this.adjList.get(v)) {
            this.addVertex(v)
        };
        if (!this.adjList.get(v)) {
            this.addVertex(w);
        };
        this.adjList.get(v).push(w);
        if (!this.isDirected) {
            this.adjList.get(w).push(v);
        }
    };
    getVertices() {
        return this.vertices;
    };
    getAdjList() {
        return this.adjList;
    };
    toString() {
        let s = '';
        for (let i = 0; i < this.vertices.length; i++) {
            s += `${this.vertices[i]}->`;
            const neighbors = this.adjList.get(this.vertices[i]);
            for (let j = 0; j < neighbors.length; j++) {
                s += `${neighbors[j]}`;
            };
            s += `/n`;
        }
        return s;
    };


}


const Color = {
    WHITE: 0,
    GREY: 1,
    BLACK: 2
};

function initializeColor(vertices) {
    const color = {};
    for (let i = 0; i < vertices.length; i++) {
        color[vertices[i]] = this.Color.WHITE;
    };
    return color;
};

function breadthFirstSearch(graph, startVertex, callback) {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(vertices);

    const queue = new Queue();
    const distances = {};
    const predecessors = {};
    queue.enqueue(startVertex);

    for (let i = 0; i < vertices.length; i++) {
        distances[vertices[i]] = 0;
        predecessors[vertices[i]] = null;
    }

    while (!queue.isEmpty()) {
        const u = queue.dequeue();
        const neighbors = adjList.get(u);
        color[u] = Color.GREY;
        for (let i = 0; i < neighbors.length; i++) {
            const w = neighbors[i];
            if (color[w] === Color.WHITE) {
                color[w] = Color.GREY;
                distances[w] = distances[u] + 1;
                predecessors[w] = u;
                queue.enqueue(w);
            };
            color[u] = color.BLACK;
        }
        return { distances, predecessors }
    }
}

// 广度优先算法
function breadthFirstSearch(graph, startVertex, callback) {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(vertices);

    const queue = [];
    queue.unshift(startVertex);

    while (!queue.isEmpty()) {
        const u = queue.shift();
        const neighbors = adjList.get(u);
        color[u] = Color.GREY;
        for (let i = 0; i < neighbors.length; i++) {
            const w = neighbors[i];
            if (color[w] === Color.WHITE) {
                color[w] = Color.GREY;
                queue.unshift(w);
            };
            color[u] = color.BLACK;
            if (callback) {
                callback(u);
            }
        }

    }
}


// 深度优先算法
function depthFirstSearch(graph, callback) {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(vertices);

    for (let i = 0; i < vertices.length; i++) {
        if (color[vertices[i]] === Color.WHITE) {
            depthFirstSearchVisit(vertices[i], color, adjList, callback);
        }
    }
};

function depthFirstSearchVisit(u, color, adjList, callback) {
    color[u] = Color.GREY;
    if (callback) {
        callback(u)
    };
    const neighbors = adjList.get(u);
    for (let i = 0; i < neighbors.length; i++) {
        const w = neighbors[i];
        if (color[w] === Color.WHITE) {
            depthFirstSearchVisit(w, color, adjList, callback);
        }
    }
    color[u] = Color.BLACK;
}


// 测试git